<?php

// Given a string of lowercase characters /^[a-z]+$/, reorder them such that the same characters are at least distance d from each other.
// Solution: 
// 1) Init an array to store the frequency of each char
// 2) Always try to put the most frequent char if possible. Can put means the previous d chars there were no occurence of char.
// 3) If such char is not found the whole function should return false;

$string = "aabbbbccddeeee";

echo $string;

echo "<br/>After:";

$result = foo($string, 2);

if( $result ){
	echo $result;	
}
else {
	echo "Cannot...";
}


// A helper function to look for next char to use, with a ng list of char
// Return -1 means not found!!
function getMaxChar( $freq, $ng ){
	$max = 0;
	$maxIndex = -1;
	for( $i=0; $i<26; $i++ ){
		if( isset($freq[$i]) ){
			if( ($freq[$i]) > $max && ($ng[$i] <= 0) ){
				$max = $freq[$i];
				$maxIndex = $i;
			}
		}
	}

	return $maxIndex;
} 

function foo( $string, $distance ){
	if( !$string || $distance >= strlen($string) ){
		// Cannot help...
		return null;
	}

	$len = strlen($string);

	// Init the freqency array
	$freq = array_fill(0, 26, 0);
	for( $i=0; $i<$len; $i++ ){
		$index = ord($string[$i]) - ord('a');
		$freq[ $index ] = $freq[ $index ] + 1;
	}

	echo implode( ', ', $freq ) . '<br/>';

	$result = '';

	$ng = array_fill(0, 26, 0);
	for( $i=0; $i<$len; $i++ ){
		$char = getMaxChar( $freq, $ng );
		if( -1 == $char ){
			return null;
		}

		// Use this one
		$result .= chr($char + ord('a'));

		$freq[$char] = $freq[$char] - 1;

		// Decrement the used array
		for( $j=0; $j<26; $j++ ){
			$ng[$j] = $ng[$j] - 1;
		}
		// Set this char as used		
		$ng[$char] = $distance;
	}

	return $result;
}